package Heap;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Heap {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        Heap heap = new Heap();
        heap.maxHeap(arr);
        System.out.println(Arrays.toString(arr));

    }

    //建立大根堆
    public void maxHeap (int[] arr) {
        int n = arr.length;
        int last = n / 2 - 1;
        //建立大根堆
        for (int i = last; i >= 0; i--) {
            down(arr,i,n);
        }

        System.out.println(Arrays.toString(arr));
        for (int i = n - 1; i > 0; i--) {
/*            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;*/
            swap(arr,i,0);

            down(arr, 0, i);
        }

    }

    //下潜
    public void down(int[] arr,int i,int n) {
        int max = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[max]) {
            max = left;
        }

        if (right < n && arr[right] > arr[max]) {
            max = right;
        }

        if (max != i) {
/*            int temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;*/
            swap(arr,i,max);

            down(arr, max, n);
        }
    }

    //交换
    public void swap (int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
